package org.xiaoxin.leetcode.string;

import java.util.*;

/**
 * 438. 找到字符串中所有字母异位词
 * <p>
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 * <p>
 * 示例 1:
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 * <p>
 * 示例 2:
 * 输入: s = "abab", p = "ab"
 * 输出: [0,1,2]
 * 解释:
 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 * <p>
 * 提示:
 * 1 <= s.length, p.length <= 3 * 10^4
 * s 和 p 仅包含小写字母
 * <p>
 * 难度：中等
 * 标签：哈希表、字符串、滑动窗口
 *
 * @author xiaoxin
 */
public class _438_FindAllAnagramsInAString {

    /**
     * 方法一：滑动窗口 + 数组计数
     * 思路：使用固定大小的滑动窗口，比较窗口内字符频率与模式串字符频率是否相同
     * 时间复杂度：O(n)，其中 n 是字符串 s 的长度
     * 空间复杂度：O(1)，因为字符集大小是固定的（26个小写字母）
     */
    public List<Integer> findAnagrams1(String s, String p) {
        // 提示：
        // 1. 使用两个大小为26的数组分别统计模式串p和当前窗口中字符的频率
        // 2. 使用固定大小的滑动窗口（大小为p的长度）在s上滑动
        // 3. 每次滑动时，更新窗口中字符的频率，并与模式串p的字符频率比较
        List<Integer> result = new ArrayList<>();

        int sLength = s.length();
        int pLength = p.length();

        if (sLength < pLength) {
            return result;
        }
        int[] pCount = new int[26];
        int[] sCount = new int[26];

        for (int i = 0; i < pLength; i++) {
            pCount[p.charAt(i) - 'a']++;
        }


        for (int i = 0; i < pLength; i++) {
            sCount[s.charAt(i) - 'a']++;
        }

        if (Arrays.equals(pCount, sCount)) {
            result.add(0);
        }

        for (int i = 0; i < sLength - pLength; i++) {
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + pLength) - 'a']++;
            if (Arrays.equals(sCount, pCount)) {
                result.add(i + 1);
            }
        }


        return result;
    }


    /**
     * 方法二：滑动窗口 + 哈希表
     * 思路：使用哈希表记录字符频率，适用于字符集较大的情况
     * 时间复杂度：O(n)，其中 n 是字符串 s 的长度
     * 空间复杂度：O(k)，其中 k 是字符集大小
     */
    public List<Integer> findAnagrams2(String s, String p) {
        // 提示：
        // 1. 使用两个HashMap分别统计模式串p和当前窗口中字符的频率
        // 2. 使用固定大小的滑动窗口在s上滑动
        // 3. 每次滑动时，更新窗口中字符的频率，并与模式串p的字符频率比较
        int sLength = s.length();
        int pLength = p.length();
        List<Integer> result = new ArrayList<>();
        if (sLength < pLength) {
            return result;
        }

        Map<Character, Integer> pMap = new HashMap<>();
        Map<Character, Integer> sMap = new HashMap<>();

        // 初始化 p

        for (char c : p.toCharArray()) {
            pMap.put(c, pMap.getOrDefault(c, 0) + 1);
        }

        // 初始化窗口
        for (int i = 0; i < pLength; i++) {
            char key = s.charAt(i);
            sMap.put(key, sMap.getOrDefault(key, 0) + 1);
        }

        if (Objects.equals(sMap, pMap)) {
            result.add(0);
        }


        // 滑动窗口
        for (int i = 0; i < sLength - pLength; i++) {
            char left = s.charAt(i);
            // 左边移动
            sMap.put(left, sMap.get(left) - 1);


            //删除为 0 的，也就是不存在了的，避免影响 map 对比
            if ((sMap.get(left) == 0)) {
                sMap.remove(left);
            }

            //右边移动
            char right = s.charAt(i + pLength);
            sMap.put(right, sMap.getOrDefault(right, 0) + 1);

            if (Objects.equals(sMap, pMap)) {
                result.add(i + 1);
            }
        }
        return result;

    }

    /**
     * 方法三：优化的滑动窗口
     * 思路：使用差异计数器，只有当所有字符频率匹配时才添加结果
     * 时间复杂度：O(n)，其中 n 是字符串 s 的长度
     * 空间复杂度：O(1)，因为字符集大小是固定的（26个小写字母）
     */
    public List<Integer> findAnagrams3(String s, String p) {
        // 提示：
        // 1. 使用一个计数器记录当前窗口与模式串p的字符频率差异数
        // 2. 只有当差异计数为0时，才表示当前窗口是p的异位词
        // 3. 这种方法避免了每次都要比较整个数组或哈希表
        List<Integer> result = new ArrayList<>();
        int sLength = s.length();
        int pLength = p.length();
        if (sLength < pLength) {
            return result;
        }

        int[] count = new int[26];
        // 代表差异字母的个数
        int diff = 0;

        //初始化
        for (int i = 0; i < pLength; i++) {
            count[s.charAt(i) - 'a']++;
            count[p.charAt(i) - 'a']--;
        }

        for (int c : count) {
            if (c != 0) {
                diff++;
            }
        }

        if (diff == 0) {
            result.add(0);
        }

        //滑动窗口
        for (int i = 0; i < sLength - pLength; i++) {
            int leftIndex = s.charAt(i) - 'a';
            // 左侧滑出
            count[leftIndex]--;
            //计算差异数,只关注 0，-1 就行，也就是目标 0 的变化
            if (count[leftIndex] == 0) {
                diff--;
            } else if (count[leftIndex] == -1) {
                diff++;
            }

            int rightIndex = s.charAt(i + pLength) - 'a';
            //右侧滑入
            count[rightIndex]++;

            if (count[rightIndex] == 0) {
                diff--;
            } else if (count[rightIndex] == 1) {
                diff++;
            }


            if (diff == 0) {
                result.add(i + 1);
            }


        }


        return result;
    }

    public static void main(String[] args) {
        testAllMethods();
    }

    /**
     * 测试所有方法
     */
    private static void testAllMethods() {
        System.out.println("=== 438. 找到字符串中所有字母异位词 - 测试用例 ===\n");

        // 示例 1
        String s1 = "cbaebabacd";
        String p1 = "abc";
        testCase("示例 1", s1, p1, Arrays.asList(0, 6));

        // 示例 2
        String s2 = "abab";
        String p2 = "ab";
        testCase("示例 2", s2, p2, Arrays.asList(0, 1, 2));

        // 额外测试用例

        // 测试用例 3：s 长度小于 p
        String s3 = "ab";
        String p3 = "abc";
        testCase("测试用例 3（s 长度小于 p）", s3, p3, Arrays.asList());

        // 测试用例 4：没有异位词
        String s4 = "hello";
        String p4 = "world";
        testCase("测试用例 4（没有异位词）", s4, p4, Arrays.asList());

        // 测试用例 5：p 只有一个字符
        String s5 = "aaaa";
        String p5 = "a";
        testCase("测试用例 5（p 只有一个字符）", s5, p5, Arrays.asList(0, 1, 2, 3));

        // 测试用例 6：s 和 p 相同
        String s6 = "abc";
        String p6 = "abc";
        testCase("测试用例 6（s 和 p 相同）", s6, p6, Arrays.asList(0));

        // 测试用例 7：p 中有重复字符
        String s7 = "ababababab";
        String p7 = "aab";
        testCase("测试用例 7（p 中有重复字符）", s7, p7, Arrays.asList(0, 2, 4, 6));

        // 测试用例 8：长字符串
        String s8 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        String p8 = "aaaaaaaaaa";
        List<Integer> expected8 = new ArrayList<>();
        for (int i = 0; i <= 40; i++) {
            expected8.add(i);
        }
        testCase("测试用例 8（长字符串）", s8, p8, expected8);
    }

    /**
     * 测试单个用例
     */
    private static void testCase(String testName, String s, String p, List<Integer> expected) {
        System.out.println(testName + ":");
        System.out.println("输入: s = \"" + s + "\", p = \"" + p + "\"");
        System.out.println("期望结果: " + expected);

        _438_FindAllAnagramsInAString solution = new _438_FindAllAnagramsInAString();

        // 测试方法一
        List<Integer> result1 = solution.findAnagrams1(s, p);
        boolean method1Correct = result1.equals(expected);
        System.out.println("方法一结果: " + result1 + " " +
                (method1Correct ? "✅" : "❌"));

        // 测试方法二
        List<Integer> result2 = solution.findAnagrams2(s, p);
        boolean method2Correct = result2.equals(expected);
        System.out.println("方法二结果: " + result2 + " " +
                (method2Correct ? "✅" : "❌"));

        // 测试方法三
        List<Integer> result3 = solution.findAnagrams3(s, p);
        boolean method3Correct = result3.equals(expected);
        System.out.println("方法三结果: " + result3 + " " +
                (method3Correct ? "✅" : "❌"));

        boolean allCorrect = method1Correct && method2Correct && method3Correct;
        System.out.println("整体测试: " + (allCorrect ? "✅ 通过" : "❌ 失败"));
        System.out.println();
    }
}